package 最少侧跳次数;

import java.util.Arrays;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-21 23:42
 **/

public class Solution {
    public int minSideJumps(int[] obstacles) {
        int len = obstacles.length;
        int[][] dp = new int[len + 1][4];
        for (int i = 1; i <= len; i++) {
            Arrays.fill(dp[i], 0x03f3f3f);
        }
        dp[1][2] = 0;
        dp[1][1] = 1;
        dp[1][3] = 1;
        for (int i = 2; i <= len; i++) {
            // 当前节点上的跑道没有石头，则直接可以由同一个跑道跳过来
            if (obstacles[i - 1] != 1) {
                dp[i][1] = dp[i - 1][1];
            }
            if (obstacles[i - 1] != 2) {
                dp[i][2] = dp[i - 1][2];
            }
            if (obstacles[i - 1] != 3) {
                dp[i][3] = dp[i - 1][3];
            }
            // 除了可以从同一个跑道的前一个节点跳过来，还可以从其它另外两个跑道侧跳过来
            if (obstacles[i - 1] != 1) {
                dp[i][1] = Math.min(dp[i][1], Math.min(dp[i][2], dp[i][3]) + 1);
            }
            if (obstacles[i-1] != 2){
                dp[i][2] = Math.min(dp[i][2], Math.min(dp[i][1], dp[i][3]) + 1);
            }
            if (obstacles[i-1] != 3){
                dp[i][3] = Math.min(dp[i][3], Math.min(dp[i][1], dp[i][2]) + 1);
            }
        }
        return Math.min(dp[len][1], Math.min(dp[len][2], dp[len][3]));
    }
}
